package main

import (
	"fmt"
	"strconv"
)

/**
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2 MB, 在所有 Go 提交中击败了77.54%的用户
 */
func getPermutation(n int, k int) string {

	f := make([]int, n)
	f[0] = 1
	for i := 1; i < n; i++ { f[i] = f[i - 1] * i }

	st := make([]bool, n + 1)
	res := ""
	for i := 0; i < n; i++ {
		for j := 1; j <= n; j++ {
			if st[j] { continue }

			if f[n - 1 - i] < k {
				k -= f[n - 1 - i]
			} else {
				res += strconv.Itoa(j)
				st[j] = true
				break
			}
		}
	}
	return res
}

func main() {

	fmt.Println(getPermutation(3, 5))  // 312
}
